/* ************************************************************************
> File Name:     LinkedList.h
# author:        
# mail:          
> created time:  2023年02月13日 星期一 20时23分16秒
> description:   
 ************************************************************************/

#ifndef LINKLIST_H
#define LINKLIST_H
#include <iostream>
#include "../include/SqList.h"
#include <unistd.h>
using namespace std;


template <typename T>
struct node
{
    T date;
    node* pNext;
};

template <typename T>
class Linklist
{
public:
    Linklist();
    Linklist(const Linklist<T> &list);
    Linklist<T>& operator= (const Linklist<T> &rhs);
    ~Linklist();
public:
    void headAdd(const T& date); //在头结点插入
    void rearAdd(const T& date); //在尾节点插入
    int size() const; //返回链表长度
    bool isEmpty() const; //判断是否为空
    void print() const; //遍历链表
    T getNElement(int n) const; //返回链表第n个节点值
    void insertNElement(int n,const T& data);//将元素插入在链表的第pos位置上;
    void deleteNElement(int n = 1); //删除第n个节点
    void modifyElement(int n, const T& date); //修改n位置的元素值为x;
    int find(const T& date); //查找x第一次出现的位置，若没有，返回-1;
    void sort(); //对链表元素进行升序排序;  
    void destroy();//销毁链表，将链表成为空链表;

private:
    node<T>* header;
    int length;

};

template <typename T>
Linklist<T>::Linklist() :header(NULL), length(0) {};

template <typename T>
Linklist<T>::Linklist(const Linklist<T> &list) : header(NULL), length(0)
{
    int i = 1;
    while (i <= list.size())
    {
        rearAdd(list.getNElement(i));
        i++;
    }
}

template <typename T>
Linklist<T>& Linklist<T>::operator= (const Linklist<T> &rhs)
{
    if (this == &rhs)
    {
        return *this;
    }
    destroy();
    for (int i = 1; i <= rhs.size(); ++i)
    {
        rearAdd(rhs.getNElement(i));
    }
    return *this;
}

template <typename T>
Linklist<T>::~Linklist()
{
    destroy();
}

template <typename T>
void Linklist<T>::headAdd(const T& date)
{
    node<T> *pnode = new node<T>;
    pnode->date = date;
    pnode->pNext = NULL;
    if (header == NULL)
    {
        header = pnode;
    }
    else
    {
        pnode->pNext = header;
        header = pnode;
    }
    length++;
}

template <typename T>
void Linklist<T>::rearAdd(const T& date)
{
    node<T> *pnode = new node<T>;
    pnode->date = date;
    pnode->pNext = NULL;
    if (header == NULL)
    {
        header = pnode;
    }
    else
    {
        node<T>* rear = header;
        while (rear->pNext != NULL)
        {
            rear = rear->pNext;
        }
        rear->pNext = pnode;        
    }
    length++;
}

template <typename T>
int Linklist<T>::size() const
{
    return length;
}

template <typename T>
bool Linklist<T>::isEmpty() const
{
    return header == NULL;
}

template <typename T>
void Linklist<T>::print() const
{
    node<T> *ptemp = header;
    int count = 0;
    while (ptemp != NULL)
    {
        std::cout << ptemp->date;
        if(ptemp->pNext != NULL) cout << " -> ";
        ptemp = ptemp->pNext;
        count++;
    }
    std::cout << std::endl;
}

template <typename T>
T Linklist<T>::getNElement(int n) const
{
    if (n < 1 || n > length)
    {
        throw "获得元素位置非法！";
    }
    else
    {
        int i = 1;
        node<T> *ptemp = header;
        while (i++ < n)
        {
            ptemp = ptemp->pNext;
        }
        return ptemp->date;
    }
}

template <typename T>
void Linklist<T>::insertNElement(int n, const T& date)
{
    if (n < 1 || n > length)
    {
        std::cout << "插入元素位置非法！" << std::endl;
    }
    else
    {
        if (n == 1)
        {
            node<T> *ptemp = new node<T>;
            ptemp->date = date;
            ptemp->pNext = header;
            header = ptemp;
        }
        else
        {
            int i = 1;
            node<T> *ptemp = header;
            while (++i < n)
            {
                ptemp = ptemp->pNext;
            }
            node<T> *pinsert = new node<T>;
            pinsert->date = date;
            pinsert->pNext = ptemp->pNext;
            ptemp->pNext = pinsert;
        }
        length++;
    }
    return;
}

template <typename T>
void Linklist<T>::deleteNElement(int n)
{
    if (n < 1 || n > length)
    {
        std::cout << "删除元素位置非法！" << std::endl;
    }
    else
    {
        node<T> *deleteElement;
        if (n == 1)
        {
            deleteElement = header;
            header = header->pNext;
        }
        else
        {
            int i = 1;
            node<T> *ptemp = header;
            while (++i < n)
            {
                ptemp = ptemp->pNext;
            }
            deleteElement = ptemp->pNext;
            ptemp->pNext = deleteElement->pNext;

        }
        delete deleteElement;
        length--;
    }
    return;
}

template <typename T>
void Linklist<T>::modifyElement(int n, const T& date)
{
    if (n < 1 || n > length)
    {
        std::cout << "修改元素位置非法！" << std::endl;
    }
    else
    {
        if (n == 1)
        {
            header->date = date;
        }
        else
        {
            node<T> *ptemp = header;
            int i = 1;
            while (i++ < n)
            {
                ptemp = ptemp->pNext;
            }
            ptemp->date = date;
        }
    }
    return;
}

template <typename T>
int Linklist<T>::find(const T& date)
{
    int i = 1;
    int re = -1;
    node<T> *ptemp = header;
    while (!ptemp)
    {
        if (ptemp->date == date)
        {
            re = i;
            break;
        }
        i++;
        ptemp = ptemp->pNext;
    }
    return re;
}

template <typename T>
void Linklist<T>::sort()
{
    if (length > 1)
    {
        for (int i = length; i > 0; --i)
        {
            for (int j = 1; j < i; j++)
            {
                T lift = getNElement(j);
                T right = getNElement(j + 1);
                if (lift > right)
                {
                    modifyElement(j, right);
                    modifyElement(j + 1, lift);
                }
            }
        }
    }
    return;
}

template <typename T>
void Linklist<T>::destroy()
{
    while (header != NULL)
    {
        node<T> *ptemp = header;
        header = header->pNext;
        delete ptemp;
    }
    length = 0;
}

template <typename T>
Linklist<T> mergeList(Linklist<T> l1, Linklist<T> l2);

template <typename T>
Linklist<T> intersectList(Linklist<T> l1, Linklist<T> l2);

void MyLinkedList();
#endif
